/**
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、
 * 直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 *
 *https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
 *

 */
class MaxValue {
    public int maxValue(int[][] grid) {
        int len=grid.length;
        int len2=grid[0].length;
        int[][] dp=new int[len][len2];
       dp[0][0]=grid[0][0];
        for(int i=0;i<len;i++){
            for(int j=0;j<len2;j++){
                if(i==0&&j==0)
                continue;
                else if(i==0){
                    dp[i][j]=grid[i][j]+dp[i][j-1];
                }
                else if(j==0){
                    dp[i][j]=grid[i][j]+dp[i-1][j];
                }else{
                    dp[i][j]=grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len-1][len2-1];
    }
}